package com.leo.basic.chapter05;

import java.util.Arrays;

/**
 *
 * @author xuexiaolei
 * @version 2017年12月04日
 */
public class DivideAndConquer {
    /**
     * 二分法求最大最小值
     * @param l     数组
     * @param i     起始下标
     * @param j     终点下标
     * @param maxAndMin     保存结果的数组，maxAndMin[0]最大值，maxAndMin[1]最小值
     */
    public static void maxMin(int[] l, int i, int j,int[] maxAndMin){
        if (i == j){
            maxAndMin[0] = maxAndMin[1] = l[i];
        }else if (i==j){
            maxAndMin[0] = l[i]>l[j]?l[i]:l[j];
            maxAndMin[1] = l[i]>l[j]?l[j]:l[i];
        }else {
            int mid = (i+j)/2;
            int[] maxAndMin1 = new int[2];
            int[] maxAndMin2 = new int[2];
            maxMin(l, i, mid, maxAndMin1);
            maxMin(l,mid+1, j, maxAndMin2);
            maxAndMin[0] = maxAndMin1[0]>maxAndMin2[0]?maxAndMin1[0]:maxAndMin2[0];
            maxAndMin[1] = maxAndMin1[1]<maxAndMin2[1]?maxAndMin1[1]:maxAndMin2[1];
        }
    }

    /**
     * 二分查找，返回找到的下标，如果没有该值，返回应当插入的位置
     * @param l
     * @param find
     * @param start
     * @param end
     * @return
     */
    public static int bSearch(int[] l, int find, int start, int end){
        if (start <= end){
            int mid = (start+end)/2;
            if (l[mid] == find){
                return mid;
            }else if (l[mid] < find){
                return bSearch(l, find, mid+1, end);
            }else{
                return bSearch(l, find, start, mid-1);
            }
        }
        return start;
//        return end-1;//都可以
    }

    /**
     * 合并
     * @param l
     * @param start
     * @param mid
     * @param end
     */
    public static void merge(int[] l, int start, int mid, int end){
        int[] temp = new int[end-start+1];
        int i=start,j=mid+1,k=0;
        while (i<=mid && j<=end){
            if (l[i]<l[j]){
                temp[k]=l[i];
                i++;
            }else {
                temp[k]=l[j];
                j++;
            }
            k++;
        }
        while (i<=mid) temp[k++]=l[i++];
        while (j<=end) temp[k++]=l[j++];
        for (int m = 0; m < temp.length; m++) {
            l[start+m]=temp[m];
        }
    }

    /**
     * 合并排序
     * @param l
     * @param start
     * @param end
     */
    public static void mergeSort(int[] l, int start, int end){
        if (start < end){
            int mid = (start+end)/2;
            mergeSort(l, start, mid);
            mergeSort(l, mid+1, end);
            merge(l, start, mid, end);
        }
    }


    public static int partition(int[] l, int start, int end){
        int temp = l[start];
        int i=start,j=end;
        while (i<j){
            while (i<j && l[j] >= temp) j--;
            l[i] = l[j];
            while (i<j && l[i] <= temp) i++;
            l[j] = l[i];
        }
        l[i]=temp;
        return i;
    }
    public static void quickSort(int[] l, int start, int end){
        if (start<end){
            int pos = partition(l, start, end);
            quickSort(l, start, pos-1);
            quickSort(l, pos+1, end);
        }
    }

    /**
     * 找到第K小元素
     * @param l
     * @param k
     * @return
     */
    public static int selectK(int[] l, int k){
        if (k<1 || k>l.length) return -1;
        int start = 0,end = l.length-1,pos=0;
        do {
            pos = partition(l, start, end);
            if (pos == k-1){
                return l[pos];
            }else if (pos < k-1){
                start = pos+1;
            }else {
                end = pos-1;
            }
        }while (true);
    }

    public static void main(String[] args) {
        int[] maxAndMim = new int[2];
        maxMin(new int[]{2,6,3,7,27,4,8,2,4,-1,3}, 0, 10, maxAndMim);
        System.out.println(Arrays.toString(maxAndMim));

        System.out.println(bSearch(new int[]{1,2,3,4,5,7,8,9,10,234,545},5, 0, 10));
        System.out.println(bSearch(new int[]{1,2,3,4,5,7,8,9,10,234,545},6, 0, 10));
        System.out.println(bSearch(new int[]{1,2,3,4,5,7,8,9,10,234,545},250, 0, 10));
        System.out.println(bSearch(new int[]{1},2, 0, 0));

        int[] a = new int[]{2,6,3,7,27,4,8,2,4,-1,3};
        mergeSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));

        a = new int[]{2,6,3,7,27,4,8,2,4,-1,3};
        quickSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));

        a = new int[]{2,6,3,7,27,4,8,2,4,-1,3};
        System.out.println(selectK(a,10));

    }
}
